/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Practica4.Practica;

import Practica4.sort.SortingAlgorithm;
import Practica4.util.Lista;
import Practica4.util.Nodo;
import java.util.Random;

/**
 *
 * @author miguel
 */
public class AlgoritmosOrdenamientos implements SortingAlgorithm {

    @Override
    public int[] mergeSort(int[] array) {
        int s = 1;
        int izq1, izq2, der1, der2;
        while (s < array.length) {
            izq1 = 1;
            while (izq1 + s <= array.length) {
                izq2 = izq1 + s - 1;
                der1 = izq2 + 1;
                if (der1 + s - 1 > array.length) {
                    der2 = array.length;
                } else {
                    der2 = der1 + s - 1;
                }
                array = mezcla(izq1, izq2, der1, der2, array);
                izq1 = der2 + 1;
                s = s * 2;
            }
        }
        return array;
    }

    @Override
    public int[] heapSort(int[] array) {
        for( int i = array.length / 2; i >= 0; i-- )  /* buildHeap */
            heapify( array, i, array.length );
        for( int i = array.length - 1; i > 0; i-- )
        {
            swap( 0, i, array );            /* deleteMax */
            heapify( array, 0, i );
        }
        return array;
    }
    
    /**
     * El valor del hijo izquierdo
     * @param i
     * @return 
     */
    private static int leftChild(int i){
        return 2*i+1;
    }
    
    /**
     * Reordena el heap
     * @param array
     * @param i
     * @param n 
     */
    private static void heapify(int[] array, int i, int n) {
        int child;
        int tmp;

        for( tmp = array[ i ]; leftChild( i ) < n; i = child )
        {
            child = leftChild( i );
            if( child != n - 1 && array[ child ]< array[ child + 1 ] ) 
                child++;
            if( tmp < array[ child ]  )
                array[ i ] = array[ child ];
            else
                break;
        }
        array[ i ] = tmp;
    }

    /**
     * Intercambia dos elementos en el arreglo dado
     *
     * @param i indice del arreglo
     * @param j indice del arreglo
     * @param array arreglo
     */
    private static void swap(int i, int j, int[] array) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    @Override
    public int[] quickSortMiddle(int[] array) {
        quickSortMiddle(array,0,array.length-1);
        return array;
    }

    @Override
    public int[] quickSortRandom(int[] array) {
        quickSortRandom(array,0,array.length-1);
        return array;
    }

    @Override
    public int[] quickSortAverage(int[] array) {
        quickSortAverage(array,0,array.length-1);
        return array;
    }

    private static void quickSortMiddle(int[] array, int a, int b){
        int j;
        if(a<b){
            j = partitionMiddle(array,a,b);
            quickSortMiddle(array,a,j-1);
            quickSortMiddle(array,j+1,b);
        }
    }
    
    private static void quickSortRandom(int[] array, int a, int b){
        int j;
        if(a<b){
            j = partitionRandom(array,a,b);
            quickSortRandom(array,a,j-1);
            quickSortRandom(array,j+1,b);
        }
    }
    
    private static void quickSortAverage(int[] array,int a, int b){
        int j;
        if(a<b){
            j = partitionAverage(array,a,b);
            quickSortAverage(array,a,j-1);
            quickSortAverage(array,j+1,b);
        }
    }
    
    
    
    private static int partitionRandom(int[] array, int a, int b) {
        int i = a, j = b;
        int tmp;
        Random r = new Random();
        
        int pivote = r.nextInt(b-a);

        while (i <= j) {
            while (array[i] < pivote) {
                i++;
            }
            while (array[j] > pivote) {
                j--;
            }
            if (i <= j) {
              
                tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
                i++;
                j--;
            }
        };

        return i;
    }

    private static int partitionMiddle(int[] array, int a, int b) {
        int i = a, j = b;
        int tmp;
        int pivote = array[(a + b) / 2];

        while (i <= j) {
            while (array[i] < pivote) {
                i++;
            }
            while (array[j] > pivote) {
                j--;
            }
            if (i <= j) {
                tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
                i++;
                j--;
            }
        }

        return i;
    }

    private static int partitionAverage(int[] array, int a, int b) {
        int i = a, j = b;
        int tmp;
        int pivot = (array[a] + array[(a + b) / 2] + array[b]) / 3;

        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
                i++;
                j--;
            }
        }

        return i;
    }

    @Override
    public int[] localInsertionSort(int[] array) {
        
        Lista L = new Lista(array[0]);
        Nodo ui = L.getCabeza();
        int i;
        for(i = 1;i<array.length;i++){
            if(ui.getValor() < array[i]){
                ui = L.insertaDerecha(ui,new Nodo(array[i]));
            }else{
                ui = L.insertaIzquierda(ui, new Nodo(array[i]));
            }
        }
        
        array = L.datos();

        return array;
    }

    @Override
    public int[] insertionSort(int[] array) {
        int j, temp;
        for (int i = 1; i != array.length; i++) {
            temp = array[i];
            for (j = i; j > 0 && array[j - 1] > temp; j--) {
                array[j] = array[j - 1];
            }
            array[j] = temp;
        }
        return array;
    }

    @Override
    public int[] shellSort(int[] array) {
        int i, j, h, v;
        h = array.length / 2;
        while (h > 0) {
            for (i = h; i < array.length; i++) {
                v = array[i];
                j = i;
                while (j >= h && array[j - h] > v) {
                    array[j] = array[j - h];
                    j = j - h;
                }
                array[j] = v;
            }
            h = h / 2;
        }

        return array;
    }

    private int[] mezcla(int izq1, int izq2, int der1, int der2, int[] array) {
        int i = izq1;
        int j = der1;
        int k = 0;
        int[] t = new int[der2 - izq1];
        while ((i <= izq2) && (j <= der2)) {
            if (array[i] < array[j]) {
                t[k++] = array[i++];
            } else {
                t[k++] = array[i++];
            }
        }

        while (i < izq2) {
            t[k++] = array[i++];
        }

        while (j < der2) {
            t[k++] = array[j++];
        }
        for (i = 0; i < k; i++) {
            array[i - 1 + izq1] = t[i];
        }
        return array;
    }
}
